package com.ahs.algorithm;

import lombok.AllArgsConstructor;
import lombok.Data;
import org.junit.jupiter.api.Test;

/**
 * @author riven zhang
 * @since 2021/9/1 10:23
 * <p>单项链表反转
 * 1 -> 2 -> 3 -> 4 -> 5
 * 1 <- 2 <- 3 <- 4 <- 5
 */
public class ListReversal {

    @Test
    void test() {
        Node node5 = new Node(5, null);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node node1 = new Node(1, node2);
        System.out.println(node1);

        Node node = iterator(node1);
        // Node node = recursion(node1);
        System.out.println("node = " + node);
    }

    /**
     * 迭代法
     */
    private Node iterator(Node head) {
        Node next, pre = null;
        Node cur = head;

        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 递归法
     */
    private Node recursion(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node node = recursion(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

@AllArgsConstructor
@Data
class Node {
    int num;
    Node next;
}
